/*
 * ============================================================================
 * 链表 (Linked List) - C语言实现
 * ============================================================================
 * 
 * 【核心定义】
 * 链表是一种线性数据结构，元素在内存中不连续存储，通过指针链接。
 * 每个节点包含数据和指向下一个节点的指针。
 * 
 * 【内存布局】
 * 单链表:
 *   head → [10|next] → [20|next] → [30|next] → [40|NULL]
 *          0x1000      0x2000      0x1500      0x3000
 * 
 * 节点在内存中的位置是随机的（非连续）
 * 每个节点包含: 数据域 + 指针域
 * 
 * struct Node {
 *     int data;           // 4字节
 *     struct Node* next;  // 8字节(64位系统)
 * };  // 总共12字节（可能对齐到16字节）
 * 
 * 【时间复杂度】
 * - 访问: O(n)  - 需要从头遍历
 * - 搜索: O(n)  - 需要遍历
 * - 插入: O(1)  - 如果已知位置
 * - 删除: O(1)  - 如果已知位置
 * 
 * 【空间复杂度】O(n) - 每个节点需要额外的指针空间
 */

#include <stdio.h>
#include <stdlib.h>

// ============================================================================
// 链表节点结构定义
// ============================================================================
typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
    int size;
} LinkedList;

// ============================================================================
// 链表基本操作
// ============================================================================

// 创建链表
LinkedList* createList() {
    LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
    list->head = NULL;
    list->size = 0;
    return list;
}

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在头部插入
void insertAtHead(LinkedList* list, int data) {
    Node* newNode = createNode(data);
    newNode->next = list->head;
    list->head = newNode;
    list->size++;
}

// 在尾部插入
void insertAtTail(LinkedList* list, int data) {
    Node* newNode = createNode(data);
    
    if (list->head == NULL) {
        list->head = newNode;
    } else {
        Node* current = list->head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
    list->size++;
}

// 在指定位置插入
void insertAt(LinkedList* list, int index, int data) {
    if (index < 0 || index > list->size) {
        printf("错误: 索引越界\n");
        return;
    }
    
    if (index == 0) {
        insertAtHead(list, data);
        return;
    }
    
    Node* newNode = createNode(data);
    Node* current = list->head;
    for (int i = 0; i < index - 1; i++) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
    list->size++;
}

// 删除头节点
void deleteAtHead(LinkedList* list) {
    if (list->head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node* temp = list->head;
    list->head = list->head->next;
    free(temp);
    list->size--;
}

// 删除指定位置的节点
void deleteAt(LinkedList* list, int index) {
    if (index < 0 || index >= list->size) {
        printf("错误: 索引越界\n");
        return;
    }
    
    if (index == 0) {
        deleteAtHead(list);
        return;
    }
    
    Node* current = list->head;
    for (int i = 0; i < index - 1; i++) {
        current = current->next;
    }
    Node* temp = current->next;
    current->next = temp->next;
    free(temp);
    list->size--;
}

// 查找元素
int search(LinkedList* list, int data) {
    Node* current = list->head;
    int index = 0;
    while (current != NULL) {
        if (current->data == data) {
            return index;
        }
        current = current->next;
        index++;
    }
    return -1;
}

// 打印链表
void printList(LinkedList* list) {
    Node* current = list->head;
    printf("[");
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) printf(" → ");
        current = current->next;
    }
    printf("]\n");
}

// 释放链表
void freeList(LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    free(list);
}

// ============================================================================
// 应用场景1: LRU缓存实现
// ============================================================================
typedef struct LRUNode {
    int key;
    int value;
    struct LRUNode* prev;
    struct LRUNode* next;
} LRUNode;

typedef struct {
    LRUNode* head;
    LRUNode* tail;
    int capacity;
    int size;
} LRUCache;

void example_lru_cache() {
    printf("\n=== 应用场景1: LRU缓存 ===\n");
    printf("场景: 最近最少使用缓存，频繁插入和删除操作\n\n");
    printf("原理:\n");
    printf("  - 使用双向链表维护访问顺序\n");
    printf("  - 最近访问的放在头部\n");
    printf("  - 容量满时删除尾部（最久未使用）\n");
    printf("  - 链表结构使插入/删除为O(1)\n");
    printf("\n优势: 动态调整，插入删除高效\n");
}

// ============================================================================
// 应用场景2: 撤销功能 (Undo)
// ============================================================================
typedef struct ActionNode {
    char action[50];
    struct ActionNode* next;
} ActionNode;

void example_undo_feature() {
    printf("\n=== 应用场景2: 文本编辑器撤销功能 ===\n");
    printf("场景: 记录用户操作历史，支持撤销\n\n");
    
    // 模拟操作历史链表
    ActionNode* history = (ActionNode*)malloc(sizeof(ActionNode));
    sprintf(history->action, "输入文字: Hello");
    history->next = NULL;
    
    ActionNode* action2 = (ActionNode*)malloc(sizeof(ActionNode));
    sprintf(action2->action, "删除3个字符");
    action2->next = history;
    
    ActionNode* action3 = (ActionNode*)malloc(sizeof(ActionNode));
    sprintf(action3->action, "输入文字: World");
    action3->next = action2;
    
    printf("操作历史（最新到最旧）:\n");
    ActionNode* current = action3;
    int step = 1;
    while (current != NULL) {
        printf("  %d. %s\n", step++, current->action);
        ActionNode* temp = current;
        current = current->next;
        free(temp);
    }
    
    printf("\n优势: 动态大小，可无限扩展历史记录\n");
}

// ============================================================================
// 应用场景3: 多项式表示
// ============================================================================
typedef struct PolyNode {
    int coefficient;  // 系数
    int exponent;     // 指数
    struct PolyNode* next;
} PolyNode;

void example_polynomial() {
    printf("\n=== 应用场景3: 多项式表示 ===\n");
    printf("场景: 表示稀疏多项式 5x^3 + 3x^2 + 7\n\n");
    
    // 创建多项式: 5x^3 + 3x^2 + 7
    PolyNode* poly = (PolyNode*)malloc(sizeof(PolyNode));
    poly->coefficient = 5;
    poly->exponent = 3;
    
    poly->next = (PolyNode*)malloc(sizeof(PolyNode));
    poly->next->coefficient = 3;
    poly->next->exponent = 2;
    
    poly->next->next = (PolyNode*)malloc(sizeof(PolyNode));
    poly->next->next->coefficient = 7;
    poly->next->next->exponent = 0;
    poly->next->next->next = NULL;
    
    printf("多项式表示: ");
    PolyNode* term = poly;
    while (term != NULL) {
        if (term->exponent > 0) {
            printf("%dx^%d", term->coefficient, term->exponent);
        } else {
            printf("%d", term->coefficient);
        }
        if (term->next != NULL) printf(" + ");
        PolyNode* temp = term;
        term = term->next;
        free(temp);
    }
    printf("\n\n优势: 只存储非零项，节省空间\n");
}

// ============================================================================
// 主函数 - 演示所有功能
// ============================================================================
int main() {
    printf("╔════════════════════════════════════════╗\n");
    printf("║   链表 (Linked List) - C语言实现      ║\n");
    printf("╚════════════════════════════════════════╝\n");
    
    // 基本操作演示
    printf("\n--- 链表基本操作 ---\n");
    LinkedList* list = createList();
    
    printf("1. 在尾部添加元素: ");
    insertAtTail(list, 10);
    insertAtTail(list, 20);
    insertAtTail(list, 30);
    printList(list);
    
    printf("2. 在头部插入元素5: ");
    insertAtHead(list, 5);
    printList(list);
    
    printf("3. 在索引2插入元素15: ");
    insertAt(list, 2, 15);
    printList(list);
    
    printf("4. 删除索引1的元素: ");
    deleteAt(list, 1);
    printList(list);
    
    printf("5. 查找元素30: 索引 = %d\n", search(list, 30));
    
    printf("\n当前链表状态:\n");
    printf("  大小: %d\n", list->size);
    printf("  每个节点内存: %lu 字节\n", sizeof(Node));
    printf("  总内存使用: %lu 字节\n", list->size * sizeof(Node));
    
    // 应用场景演示
    example_lru_cache();
    example_undo_feature();
    example_polynomial();
    
    // 优势与局限
    printf("\n╔════════════════════════════════════════╗\n");
    printf("║   优势与局限                           ║\n");
    printf("╚════════════════════════════════════════╝\n");
    printf("\n✅ 优势:\n");
    printf("  1. 动态大小，无需预分配\n");
    printf("  2. 插入/删除操作O(1)（已知位置）\n");
    printf("  3. 不需要连续内存空间\n");
    printf("  4. 易于扩展和重组\n");
    
    printf("\n⚠️ 局限:\n");
    printf("  1. 访问元素需要O(n)时间\n");
    printf("  2. 每个节点需要额外指针空间\n");
    printf("  3. 不支持随机访问\n");
    printf("  4. 缓存不友好，内存访问跳跃\n");
    
    printf("\n💡 最佳使用场景:\n");
    printf("  - 频繁插入和删除操作\n");
    printf("  - 数据量动态变化\n");
    printf("  - 不需要随机访问\n");
    printf("  - LRU缓存、撤销功能、播放列表\n");
    
    // 清理
    freeList(list);
    
    return 0;
}
